/**
 * 剑指 Offer 46. 把数字翻译成字符串（青蛙跳台阶问题抽象版）
 * https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
 */
public class Solutions_Offer_46 {
    public static void main(String[] args) {
//        int num = 12258;  // output: 5
        int num = 1234;  // output: 3
//        int num = 1204;  // output: 3
//        int num = 0;  // output: 1
//        int num = 25;  // output: 2

        int result = translateNum(num);
        System.out.println(result);
    }

    /**
     * 状态转移方程推理过程：
     * 例如 num = 1234 时，字符串为 "1234"
     * 第一个字符为 1：仅有一种方法 {1}
     * 第二个字符为 2：仅有两种不同方法 {{1,2}, {12}}
     * 第三个字符为 3：仅有三种不同方法 {{1,23}, {1,2,3}, {12,3}}
     *              因为 3 与前一字符 2，可以翻译成 23，即字母 "x"，那么可以利用第一个字符 1 的结果
     *              使 123 翻译成 {1,23}，得到一种方法
     *              而第三个字符上，不论是什么，都可以与前一字符 2 得到相同的翻译方法，即在前一字符的
     *              翻译结果后面，加上当前字符，如 {{1,2,3}, {12,3}}（前一字符能够翻译成 n 次，那么当前字符也至少可以翻译成 n 次）
     * 第四个字符为 4：仅有三种不同方法 {{1,23,4}, {1,2,3,4}, {12,3,4}}
     *              因为 4 与前一字符 3，得到 34，是无法翻译成字母的，那么 4 就只有单独翻译成一个字母 'e'
     *              于是，就与前一字符的翻译结果数相同（在前一字符的所有翻译结果后面，加上当前字符）
     *              得到：{1,23} + 4 -> {1,23,4}
     *                  {1,2,3} + 4 -> {1,2,3,4}
     *                  {12,3} + 4 -> {12,3,4}
     */
    public static int translateNum(int num) {
        String numStr = String.valueOf(num);
        int len = numStr.length();
        int[] dp = new int[len + 1];
        // dp[0] 给定默认值 1
        // dp[1] = 1：表示在字符串 numStr 中，第一个字符(索引为 0)上，有 1 种不同的翻译方法
        dp[0] = dp[1] = 1;
        // 记录遍历字符的前一字符，方便计算数值
        char c = numStr.charAt(0);

        // 从第 2 个字符（索引 1），开始遍历
        for (int i = 2; i <= len; i++) {
            // 取当前遍历字符
            char k = numStr.charAt(i - 1);
            int n = ((c - '0') * 10) + k - '0';
            // 前一字符能够翻译成 n 次，那么当前遍历也最少可以翻译成 n 次
            dp[i] = dp[i - 1];
            // 关键：判断当前字符，是否能与前一字符，组成一个字母（大于等于 10，小于等于 25）
            if (n >= 10 && n <= 25) {
                dp[i] += dp[i - 2];
            }
            // 当前遍历字符作为下一遍历字符的前一字符
            c = k;
        }
        return dp[len];
    }
}
